package BSTTree1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BSTTree1 {

    BSTNode root; // 根节点

    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
public Object get(int key){
     return doGet(root,key);
}
//递归
    private Object doGet(BSTNode node, int key){
       if(node == null){
           return null;
       }
       if(key < node.key){
           return doGet(node.left,key); //向左找
           }
       else if(node.key < key){
           return doGet(node.right,key); //向右找
       }
       else{
           return node.value;
       }
    }
    //非递归
   /* public Object get(int key){
        BSTNode node = root;
        while(node != null){
            if(key < node.key){
                node = node.left;
            }
            else if(key > node.key){
                node = node.right;
            }
            else{
                return node.value;
            }
        }
        return null;
    }*/
    public Object min(){
        return doMin(root);
    }
    public Object doMin(BSTNode node){
        if(node == null){
            return null;
        }
        if(node.left == null){
            return node.value;
        }
        return doMin(node.left);
    }
    private Object min(BSTNode node){
        if(node == null){
            return null;
        }
        BSTNode p = node;
        while (node.left != null){
            p = p.left;
        }
        return p.value;
    }
    public Object max(){
        return doMax(root);
    }
    public Object doMax(BSTNode node){
        if(node == null){
            return null;
        }
        if(node.right == null){
            return node.value;
        }
        return doMax(node.right);
    }
    //存储关键字和对应值
    public void put(int key,Object value){
        BSTNode node = root;
        BSTNode parent = null;
        while(node != null){
            parent = node;
            if(key < node.key){
                node = node.left;
            }
            else if(key > node.key){
                node = node.right;
            }
            else{
              node.value = value;
              return;
            }
        }
        if(parent == null){
        root = new BSTNode(key,value);
        return;
}
        if(key < parent.key){
            parent.left = new BSTNode(key,value);
        }else{
            parent.right = new BSTNode(key,value);
        }
    }
    public Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node.value;
    }
    public Object predecessor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromLeft = null;
        while (p != null) {
            if (key < p.key) {
                // 如果 key 小于当前节点的 key，向左子树移动。
                p = p.left;
            } else if (p.key < key) {
                // 如果当前节点的 key 小于 key，将当前节点作为可能的前驱记录，并向右子树移动。
                ancestorFromLeft = p;
                p = p.right;
            } else {
                // 当找到键值时，检查左子树以找到前驱。
                if (p.left != null) {
                    // 如果有左子树，前驱是左子树中最大的节点。
                    return max(p.left);
                }
                // 如果没有左子树，返回 null，因为没有前驱。
                return null;
            }
        }
        // 如果在 while 循环结束后没有找到 key，那么 ancestorFromLeft 就是 key 的前驱。
        return ancestorFromLeft != null ? ancestorFromLeft.value : null;
    }
    public Object successor(int key){
        BSTNode p = root;
        BSTNode ancestorFromRight = null;
        while (p != null) {
            if (key < p.key) {
                ancestorFromRight = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                if (p.right != null) {
                    return min(p.right);
                }
                return null;
            }
        }
        return ancestorFromRight != null ?
                ancestorFromRight.value : null;
    }
    public Object delete(int key){
        BSTNode p = root;
        BSTNode parent = null;
        while(p != null){
            if(key < p.key){
                parent = p;
                p = p.left;
            }else if(p.key < key){
                parent = p;
                p = p.right;
            }else{
                break;
            }
        }
        if(p == null){
            return null;
        }
        //删除操作
        if(p.left == null){
            //情况1 有右子树 无左子树
            shift(parent,p,p.right);
        }else if(p.right == null){
            //情况2 有左子树 无右子树
            shift(parent,p,p.left);
        }else{
            //情况4  左右子树都有
            //被删除节点找后继
            BSTNode s = p.right;
            BSTNode sParent = p;
            while(s.left != null){
                sParent = s;
                s = s.left;
            }
            //后继结点即为s
            if(sParent != p){
                //删除和后继不相邻，处理后继的后事
                shift(sParent,s,s.right);
                s.right = p.right;
            }
            //后继取代被删除节点
            shift(parent,p,s);
            s.left = p.left;
        }
        return p.value;
    }
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child){
        if(parent == null){
            root = child;
        }else if (deleted == parent.left){
            parent.left = child;
        }else{
            parent.right = child;
        }
    }
    //找小于key的所有vaule
    public List<Object> less(int key){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty() ){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                BSTNode pop = stack.pop();
                //处理值
                if(pop.key < key){
                    result.add(pop.value);
                }else{
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }
    //找大于key的所有value
    public List<Object> greater(int key){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty()){
            if(p != null){
                stack.push(p);
                p = p.right;
            }else{
                BSTNode pop = stack.pop();
                //处理值
                if(pop.key > key){
                    result.add(pop.value);
                }else{
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }
    //找大于等于key1并且小于等于key2的所有value
    public List<Object> between(int key1,int key2){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty()){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                BSTNode pop = stack.pop();
                //处理值
                if(pop.key >= key1 && pop.key <= key2){
                    result.add(pop.value);
                }else if(pop.key > key2){
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }
}
